#include <iostream>
#include <string>

// 最长回文子串

using namespace std;

// 暴力法
// 时间复杂度 O(n^3)
// 空间复杂度 O(1)
namespace S1 {
class Solution {
public:
    string longestPalindrome(string s) {
        
        if (s.empty()) {
            return "";
        }

        string result = "";
        int maxLength = 0;

        for (int i = 0; i < s.size(); i++) {
            for (int j = i + 1; j < s.size(); j++) {
                if (isPalindrome(s, i, j)) {
                    string sub = s.substr(i, j - i + 1);
                    if (sub.size() > maxLength) {
                        maxLength = sub.size();
                        result = sub;
                    }
                }
            }
        }
        return result;
    }

    bool isPalindrome(const string &s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
};
}




int main() {
    S1::Solution solution;
    string input = "babad";
    string result = solution.longestPalindrome(input);
    printf("Longest Palindrome Substring: %s\n", result.c_str());
    
    return 0;




}

